package com.klun.project.common.constans.leetcode;


/**
 * 给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
 * 以任意顺序返回这两个数字均可。
 */
public class Solution17d19 {
	// 等差数列求和公式 n(n+1)/2
	public int[] missingTwo(int[] nums) {
		int n = nums.length + 2, cer = n * (n + 1) / 2;
		for (int i = 0; i < nums.length; i++) {
			cer -= nums[i];
		}
		int sumTwo = cer;
		int t = cer / 2;
		cer = t * (t + 1) / 2;
		for (int num : nums) {
			if (num <= t) {
				cer -= num;
			}
		}
		return new int[]{cer, sumTwo - cer};
	}
	public static void main(String[] args) {
		Solution17d19 solution9 = new Solution17d19();
		int[] nums = {2, 3};
		int[] ints = solution9.missingTwo(nums);
		System.out.println(ints[0]);
		System.out.println(ints[1]);
	}
}
